#include <iostream>

void quick_common(int a[], int left, int right) {
    if(left >= right) { // 添加递归终止条件
      return;
    }

    int pivot = a[right];

    int i = left;
    for(int j = left; j < right; j++) {
        if(a[j] < pivot) { // 只关注小于pivot的部分
           std::swap(a[i++], a[j]);
        }
    }

    std::swap(a[i], a[right]); // // 将pivot放到正确的位置

    quick_common(a, left, i - 1);
    /*
     quick_common(a, left, i);
     无限递归：由于i的位置是pivot（基准值）经过交换后的新位置，这意味着pivot已经被放置在其最终位置，即所有在pivot左侧的元素都比它小，
     所有在pivot右侧的元素都比它大。如果递归调用时包含i，那么在处理左侧数组时，pivot元素会被再次包含在内，
     这将导致函数尝试对一个已经在正确位置上的元素进行排序，从而形成无限递归，最终导致栈溢出错误。
    */
    quick_common(a, i + 1, right);
}

/*
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

*/

void quick_sort(int a[], int left, int right)
{
    
    // int i = left, j = right;
    // int base = a[left];  
    
    if(left < right)
    {
    std::swap(a[left],a[(left+right)/2]);  
    int i = left, j = right;
    int base = a[left];  

     while(i < j)
      {
        while(i < j &&  a[j] >= base)
          j--;
        if(i < j)
         a[i++] = a[j];  //i++向左边开始收缩 

        while(i < j && a[i] <= base)
           i++;
        if(i < j)
          a[j--] = a[i]; //j--右边开始向内收缩
      }
    
    a[i] = base;

    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
  } 
}


int main()
{
   int a[] = {72,6,57,88,60,42,83,73,48,85};
   
   //quick_sort(a, 0, 9);
   quick_common(a, 0, 9);
   for(int value : a)
        std::cout << value << " ";
}
